//binaryHeap.c
#include "binaryHeap.h"
#include <stdlib.h>
PriorityQueue Initialize(int MaxElements)
{
    PriorityQueue H;
    if (MaxElements < MinPQSize)
    {
        printf("Priority queue size is too small\n");
        exit(0);
    }
    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL)
    {
        printf("Malloc failed\n");
        exit(0);
    }

    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;
    return 0;
}

void Insert(ElementType X, PriorityQueue H)
{
    int i;
    if (IsFull(H))
    {
        printf("Priority is full\n");
        exit(1);
    }

    //Insert hole into heap at the next free place.Try to place x in the hole, if x
    //doesn't destory the nature of x's father tree,complete.Else exchange the place of
    //x and x's father node,and go on.
    //We place the smallest of heap at index 1,the index 0 has a sentinel which should
    //be smaller
    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)
    {
        H->Elements[i] = H->Elements[i / 2];
    }
    H->Elements[i] = X;
}

ElementType DeleteMin(PriorityQueue H)
{
    int i, Child;
    ElementType MinElement, LastElement;
    if (isEmpty(H))
    {
        printf("Priority is empty\n");
        exit(1);
    }
    //the root node's index is 1,it must be delete
    //the last node must be mov,because the size of heap has descease by 1
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    //percolate down
    //when we delete the root node, it change to a hole.To fill it with suitable member we should select one of
    //its children or the lastelement. A new hole will appearance at the place of the child and we should try to fill it... And go on until
    //the hole have no child.
    for (i = 1; i * 2 <= H->Size; i = Child)
    {
        //the place of its child
        Child = i * 2;
        //we should select the little child
        //如果这个父节点的子节点个数是是两个，并且右边的比左边的小，我们就找到右边的子节点
        if (Child != H->Size && H->Elements[Child + 1] < H->Elements[Child])
        {
            Child++;
        }

        //if the last element is smaller than the hole's children, we directly use it to fill the hole
        //else we use the smaller child
        if (LastElement > H->Elements[Child])
        {
            H->Elements[i] = H->Elements[Child];
        }
        else
        {
            break;
        }
    }
    H->Elements[i] = LastElement;
    return MinElement;
}
